package 剑指II;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-10
 **/

public class Jz028展平多级双向链表 {

    /**
     * 多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，
     * 可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，
     * 如下面的示例所示。
     * 给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，
     * 使所有结点出现在单级双链表中。
     * <p>
     * 示例 1：
     * 输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
     * 输出：[1,2,3,7,8,11,12,9,10,4,5,6]
     * 解释：
     * 输入的多级列表如下图所示：
     * 扁平化后的链表如下图：
     * 示例 2：
     * 输入：head = [1,2,null,3]
     * 输出：[1,3,2]
     * 解释：
     * 输入的多级列表如下图所示：
     * <p>
     * 1---2---NULL
     * |
     * 3---NULL
     * 示例 3：
     * 输入：head = []
     * 输出：[]
     * 如何表示测试用例中的多级链表？
     * <p>
     * 以 示例 1 为例：
     * <p>
     * 1---2---3---4---5---6--NULL
     * |
     * 7---8---9---10--NULL
     * |
     * 11--12--NULL
     * 序列化其中的每一级之后：
     * [1,2,3,4,5,6,null]
     * [7,8,9,10,null]
     * [11,12,null]
     * 为了将每一级都序列化到一起，我们需要每一级中添加值为 null 的元素，以表示没有节点连接到上一级的上级节点。
     * [1,2,3,4,5,6,null]
     * [null,null,7,8,9,10,null]
     * [null,11,12,null]
     * 合并所有序列化结果，并去除末尾的 null 。
     * [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
     *  
     * 提示：
     * 节点数目不超过 1000
     * 1 <= Node.val <= 10^5
     */

    public Node flattenGood(Node head) {
        if (head == null) {
            return null;
        }
        this.dfsGood(head);
        return head;
    }

    private Node dfsGood(Node node) {

        Node cur = node;
        Node last = node;

        while (cur != null && (cur.next != null || cur.child != null)) {

            if (cur.child != null) {
                // 获取孩子末尾的节点, 末尾节点应该连接next
                Node cN = this.dfsGood(cur.child);
                Node next = cur.next;
                // 扁平正向连接
                cur.next = cur.child;
                // 扁平反向连接
                cur.child.prev = cur;
                // 去除孩子指针
                cur.child = null;
                // 连续正向连接
                cN.next = next;
                if (next != null) {
                    // 连续反向连接
                    next.prev = cN;
                    cur = next;
                }
            } else {
                // 直接下一个节点
                cur = cur.next;
            }
            last = cur;
        }

        // 关键点: 返回末尾的节点
        return last;
    }

    private List<Node> list = new ArrayList<>();

    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }
        this.dfs(head);
        Node temp = new Node();
        Node pre = temp;
        for (Node node : this.list) {
            pre.next = node;
            node.prev = pre;
            node.next = null;
            node.child = null;
            pre = node;
        }
        head.prev = null;
        return temp.next;
    }

    private void dfs(Node node) {
        if (node == null) {
            return;
        }
        this.list.add(node);
        this.dfs(node.child);
        this.dfs(node.next);
    }

    static class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;

        public Node() {

        }

        public Node(int val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        node1.child = node2;
        node2.child = node3;
        // 1 2 3 5 6 4
        Jz028展平多级双向链表 n = new Jz028展平多级双向链表();
        n.flattenGood(node1);
    }

}
